1. Field of the Invention
This invention relates in general to computer-implemented database systems, and, in particular, to efficient groupby aggregation in tournament tree sort.
2. Description of Related Art
Databases are computerized information storage and retrieval systems. A Relational Database Management System (RDBMS) is a database management system (DBMS) which uses relational techniques for storing and retrieving data. Relational databases are organized into tables which consist of rows and columns of data. The rows are formally called tuples or records. A database will typically have many tables and each table will typically have multiple tuples and multiple columns. The tables are typically stored on direct access storage devices (DASD), such as magnetic or optical disk drives for semi-permanent storage.
The SQL interface has evolved into a standard language for RDBMS software and has been adopted as such by both the American National Standards Institute (ANSI) and the International Standards Organization (ISO). The SQL interface allows users to formulate relational operations on the tables either interactively, in batch files, or embedded in host languages, such as C and COBOL. SQL allows the user to manipulate the data.
An example query, typical of many decision support database applications, expressed in SQL is: EQU SELECT DEPT, AVG(SALARY) FROM EMP GROUPBY DEPT
To execute the above SELECT query, the RDBMS may sort records by DEPT and compute the SALARY averages for the group of records for each DEPT. In particular, when sorting a large number of rows, there may be many parallel sorts occurring separately. These sorts may be responding to the same or different queries. Each sort takes up system resources. In particular, each sort reads a number of records, sorts these records, and places the sorted records into a temporary data set. For a large number of records, there could be many temporary data sets, which may take up the entire memory, even before the sorting is completed.
It has been suggested that special treatment be given to aggregation in a RDBMS in A. Klug, "Access Path in the Abell Statistical Query Facility", Proc. ACM SIGMOD, 1982, pp. 161-172, which is incorporated by reference herein. One technique, not suggested in the Klug article, but suggested in D. J. Haderle and E. J. Lynch, "Evaluation of Column Function on Grouped Data During Data Ordering", IBM Technical Disclosure Bulletin, 10, March 1990, p385-386, which is incorporated by reference herein, is to perform the operations related to the aggregation within a sort.
One problem pertains to doing aggregation within a sort using a tournament tree. A tournament tree is a binary tree that has been a favored sort technique because it is based on a technique called replacement/selection, which generates sort runs that are typically twice the size of main memory devoted to the sort, thereby possibly reducing the merge activity. The tournament tree sort is also favored because special hardware assists are known to speed up tournament tree sorts.
In one technique for aggregation within a sort, known as "aggregation push-down into sort", consecutive winners (e.g., for data elements, such as keys, a wilmer may be the data element having the lowest value) of tournaments are compared, and, if the winners are identical, the aggregation operations (e.g., sums and counts) are accumulated for these two keys. The technique proceeds recursively, with the key of the aggregate being the key against which the next winner is compared. A group break is detected when a non-matching key emerges as the new winner. Then, a new group begins, with the initialization of a new accumulator and count variables. This approach is referred to as "winner aggregation".
The problem with the winner aggregation approach is that several runs of different groups could be formed, even if the number of groups is less than the number of leaf nodes in the tournament tree. Once runs are formed, each run has to be inserted into a separate, temporary data set and fetched later for merging, thus causing CPU overhead. Temporary data sets occupy main memory, and when their memory requirements exceed memory, they cause input/output (I/O) interruptions.
Therefore, there is a need in the art for an improved technique for groupby aggregation in tournament tree sort.